package writtenTraining.day10;

import java.util.*;

/**
 * day10：（1）中心扩展思想 + 贪心：OR26 最长回文子串
 */

public class Solution {

    public int getLongestPalindrome (String A) {
        // 中心扩展思想 + 贪心

        int ret = 0;
        int len = A.length();
        char[] str = A.toCharArray();
        for (int i = 0; i < len; i++) {
            // 更新每一个中心位置的结果
            ret = Math.max(ret, getPalindCount(str, i));
        }

        return ret;
    }

    private int getPalindCount(char[] str, int mid) {
        int ret = 1;
        int left = mid, right = mid;

        // 检查奇数回文子串
        while (left >= 0 && right < str.length
                && str[left] == str[right]) {
            left--;
            right++;
        }
        // 更新长度
        ret = Math.max((right - left - 1), ret);

        // 检查偶数回文子串
        left = mid;
        right = mid + 1;
        while (left >= 0 && right < str.length
                && str[left] == str[right]) {
            left--;
            right++;
        }
        // 更新长度
        ret = Math.max((right - left - 1), ret);


        return ret;
    }
}

/**
 * day10:(1)动态规划思想 + 区间dp + 分类讨论 + 字符串boolean模型:OR26 最长回文子串
 */


 class Solution1 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param A string字符串
     * @return int整型
     */
    public int getLongestPalindrome (String A) {
        // 动态规划思想 + 区间dp + 分类讨论 + 字符串boolean模型
        int len = A.length();
        char[] str = A.toCharArray();
        // 创建dp
        boolean[][] dp = new boolean[len][len];
        // 初始化
        // 填表 从下往上遍历
        int maxLen = -1;
        for(int i = len - 1; i >= 0;i-- ){
            for(int j = i; j < len; j++) {
                if(str[i] == str[j]) {
                    // 查找[i,j]位置的子串是否回文
                    // 分类讨论
                    // 相邻，相同，相隔
                    dp[i][j] = i + 1 < j ?   dp[i + 1][j - 1] : true;
                }

                // 如果该位置回文就更新最大长度
                if(dp[i][j]) {
                    maxLen = Math.max(j - i + 1,maxLen);
                }
            }
        }
        // 返回值



        return maxLen;
    }
}



/**
 * day10:(2)贪心：DP30 买卖股票的最好时机(一)
 */



 class Main1 {
    public  static void main(String[] args) {
        // 贪心
        int INF = 0x3f3f3f3f;
        int minNum = INF;
        // 输入并贪心
        Scanner in = new Scanner(System.in);
        int k = in.nextInt();
        int ret = -INF;
        for(int i = 0; i < k ; i++) {
            int num = in.nextInt();
            // 获取前面的最小成本
            minNum = Math.min(minNum, num);
            // 贪心最大结果
            ret = Math.max(ret,num - minNum);
        }


        // 输出结果
        System.out.println(ret);
    }
}


/**
 * day10:(3)动态规划 + 机器人模型：DP13 [NOIP2002 普及组] 过河卒
 */



 class Main2 {
    public static void main(String[] args) {
        // 动态规划 + 机器人模型

        // 输入
        Scanner in = new Scanner(System.in);
        int n = in.nextInt() + 1, m = in.nextInt()  + 1
                , x = in.nextInt(), y = in.nextInt();

        // 创建 dp
        long[][]dp = new long[n+1][m+1];
        // 初始化
        dp[0][1] = 1;
        // 填表
        for(int i = 0; i < n ; i++) {
            for(int j = 0; j < m ; j++) {
                // 注意下标映射的关系·
                // 并注意该位置是否是过河卒的位置
                if( (i == x && j  == y)
                        || (x != i &&  y != j &&
                        (Math.abs(i  - x) + Math.abs(j - y)) == 3)) {

                } else {
                    dp[i + 1][j + 1] = dp[i][j+1] + dp[i + 1][j];
                }

            }

        }
        // 返回值
        System.out.println(dp[n][m]);
    }
}
